import java.util.Stack;

public class StackTest {
    //栈面试题
    /*
    * @ NO.1 括号匹配问题
    * */
    public boolean isValid(String str) {
        //定义一个栈
        Stack<Character> stack = new Stack<>();
        //遍历字符串
        for (int i = 0; i < str.length(); i++) {
            char chLeft = str.charAt(i);
            //判断是不是左括号
            if (chLeft == '(' || chLeft == '[' || chLeft == '{') {
                //为左括号 - 压栈
                stack.push(chLeft);
            }else {
                //为右括号 - 判断栈是不是空
                if (stack.isEmpty()) {
                    return false;
                }
                //判断右括号是否匹配
                char chright = stack.peek();//看一眼栈顶元素
                if (chright == '[' && chLeft == ']' || chright == '(' && chLeft == ')' || chright == '{' && chLeft == '}') {
                    //匹配成功 - 弹出队头元素
                    stack.pop();
                }else {
                    //不匹配
                    return false;//不是有效的括号
                }
            }
        }
        //若字符串遍历完成但是栈不为空说明左括号较多
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }

    /*
     * @ NO.2 栈的压入、弹出序列1
     */
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        //定义栈
        Stack<Integer> stack = new Stack<>();
        //遍历入栈序列
        int j = 0;//遍历出栈序列
        for (int i = 0; i < pushA.length; i++) {
            //压栈
            stack.push(pushA[i]);
            //出栈序列的j不能超过数组长度，栈不能是空
            while (j < popA.length && !stack.empty() && stack.peek() == popA[j]) {
                //弹出后j++
                stack.pop();
                j++;
            }
        }
        //如果栈为空则匹配 - 不为空则不匹配
        return stack.empty();
    }

    /*
     * @ NO.2 栈的压入、弹出序列2
     */
    public boolean IsPopOrders(int [] pushA, int [] popA) {
        int n = pushA.length;
        //辅助栈
        Stack<Integer> s = new Stack<>();
        //遍历入栈的下标
        int j = 0;
        //遍历出栈的数组
        for (int i = 0; i < n; i++) {
            //入栈：栈为空或者栈顶不等于出栈数组
            while (j < n && (s.isEmpty() || s.peek() != popA[i])) {
                s.push(pushA[j]);
                j++;
            }
            //栈顶等于出栈数组
            if (s.peek() == popA[i])
                s.pop();
                //不匹配序列
            else
                return false;
        }
        return true;
    }

    /*
     * @ NO.3 逆波兰表达式求值
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        //1.遍历数组判断当中的字符串类型
        for (int i = 0; i < tokens.length; i++) {
            if (!isOperation(tokens[i])) {
                //是数字 - 将字符串中的字符转换成整数压入
                stack.push(Integer.parseInt(tokens[i]));
            } else {
                //数操作符
                //弹出两个栈顶的元素
                int num2 = stack.pop();
                int num1 = stack.pop();
                //计算
                switch (tokens[i]) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }

        }
        return stack.pop();
    }

    private boolean isOperation(String s) {
        //比较数组当中字符是数字还是操作符
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
            return true;
        } else {
            return false;
        }
    }
}
